package leetcode_2701_2800;

import java.util.*;

public class LeeCode_2736 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(maximumSumQueries
                (new int[]{4, 3, 1, 2}, new int[]{2, 4, 9, 5}, new int[][]{{4, 1}, {1, 3}, {2, 5}})));
        System.out.println(Arrays.toString(maximumSumQueries
                (new int[]{3,2,5}, new int[]{2,3,4}, new int[][]{{4, 4}, {3, 2}, {1, 1}})));
        System.out.println(Arrays.toString(maximumSumQueries
                (new int[]{2,1}, new int[]{2,3}, new int[][]{{3,3}})));
    }
    private static int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
        Integer[] is = new Integer[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            is[i] = i;
        }
        Arrays.sort(is, (o1, o2) -> nums1[o2] - nums1[o1]);
        Deque<int[]> deque = new ArrayDeque<>();
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int index = 0;
        int ql = queries.length;
        Integer[] is2 = new Integer[ql];
        for (int i = 0; i < ql; i++) {
            is2[i] = i;
        }
        Arrays.sort(is2, (o1, o2) -> queries[o2][0] - queries[o1][0]);
        Arrays.sort(queries, (o1, o2) -> o2[0] - o1[0]);
        int index2 = 0;
        int[] ans = new int[ql];
        for (int[] q : queries) {
            while (index < is.length && nums1[is[index]] >= q[0]) {
                int x = nums1[is[index]], y = nums2[is[index]];
                if (!deque.isEmpty() && deque.peek()[0] >= y) {
                    index++;
                    continue;
                }
                while (!deque.isEmpty() && deque.peek()[1] < x + y) {
                    int[] p = deque.pop();
                    map.remove(p[0]);
                }
                deque.push(new int[]{y, x + y});
                if (!map.containsKey(y))
                    map.put(y, x + y);
                index++;
            }
            Integer key = map.higherKey(q[1] - 1);
            ans[is2[index2]] = key == null ? -1 : map.get(key);
            index2++;
        }
        return ans;
    }
}